using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; using System.Collections; namespace Multi_Robot { public partial class Form1 : Form { #region GLOBAL VARIABLES Bitmap bmp; Graphics g; bool[,] Obstacle; int[,] EndPoints; int n = 0, m = 0, K = 0; int width = 0, height = 0; int Xresolution = 1000, Yresolution = 700; int step = 10; bool EnterObstacleMode = false; ArrayList[] Paths; #endregion #region INITIALIZE public Form1() { InitializeComponent(); } private void Form1_Load(object sender, EventArgs e) { //button7.Enabled = false; button2.Hide(); button6.Hide(); button7.Hide(); checkBox1.Hide(); checkBox2.Hide(); checkBox3.Hide(); checkBox4.Hide(); checkBox5.Hide(); button3.Hide(); button4.Hide(); button5.Hide(); EndPoints = null; Obstacle = null; //textBox3.Hide(); //label2.Hide(); bmp = new Bitmap(1030, 730); g = Graphics.FromImage(bmp); g.Clear(Color.White); pictureBox1.Image = bmp; } #endregion #region MOUSE EVENTS private void pictureBox1_MouseDown(object sender, MouseEventArgs e) { if (EnterObstacleMode == false) return; if (e.Button == MouseButtons.Left) { int x = e.X - 20; int y = e.Y - 20; if (x >= 0 && y >= 0 && x < n * step && y < m * step) { int cellx = (int)(x / step); int celly = (int)(y / step); if (cellx > 0 && cellx < n - 1 && celly > 0 && celly < m - 1) { if (Obstacle[celly, cellx] == false) { for (int k = 0; k < 2 * K; k++) if (EndPoints[k, 0] == celly && EndPoints[k, 1] == cellx) { MessageBox.Show("Don't click on the source and destination points!"); return; } Obstacle[celly, cellx] = true; SolidBrush blackbrush = new SolidBrush(Color.Black); g.FillRectangle(blackbrush, cellx * step + 20, celly * step + 20, step, step); blackbrush.Dispose(); } else { Obstacle[celly, cellx] = false; Pen blackPen = new Pen(Color.Black, 1); blackPen.DashStyle = System.Drawing.Drawing2D.DashStyle.Dot; SolidBrush whitebrush = new SolidBrush(Color.White); //g.DrawRectangle(blackPen, cellx * step + 20, celly * step + 20, step, step); g.FillRectangle(whitebrush, cellx * step + 20, celly * step + 20, step, step); g.DrawRectangle(blackPen, cellx * step + 20, celly * step + 20, step, step); blackPen.Dispose(); } } } } else if (e.Button == MouseButtons.Right) { int x = e.X - 20; int y = e.Y - 20; if (x >= 0 && y >= 0 && x < n * step && y < m * step) { int cellx = (int)(x / step); int celly = (int)(y / step); if (cellx > 0 && cellx < n - 1 && celly > 0 && celly < m - 1) if (Obstacle[celly, cellx] == false) { int k = 0; while (EndPoints[k, 0] != -1) { k++; if (k == 2 * K) { MessageBox.Show("There are " + K.ToString() + " robots now!!!"); return; } } for (int i = 0; i < k; i++) if (EndPoints[i, 0] == celly && EndPoints[i, 1] == cellx) return; EndPoints[k, 0] = celly; EndPoints[k, 1] = cellx; button3.Show(); SolidBrush yellowbrush = new SolidBrush(Color.Yellow); SolidBrush Redbrush = new SolidBrush(Color.Red); SolidBrush Bluebrush = new SolidBrush(Color.Blue); if (k < 2) g.FillRectangle(Redbrush, cellx * step + 20, celly * step + 20, step, step); else if (k < 4) g.FillRectangle(Bluebrush, cellx * step + 20, celly * step + 20, step, step); else g.FillRectangle(yellowbrush, cellx * step + 20, celly * step + 20, step, step); string s = ((k / 2) + 1).ToString(); if (k % 2 == 0) s = "s" + s; else s = "g" + s; int fontsize = (int)(step / 6) + 2; if (fontsize < 5) fontsize = 5; g.DrawString(s, new Font("Verdana", fontsize), new SolidBrush(Color.Black), new Point(cellx * step + 20, celly * step + 20)); if (k + 1 == 2 * K) { button2.Show(); button6.Show(); button7.Show(); checkBox1.Show(); checkBox2.Show(); checkBox3.Show(); checkBox4.Show(); checkBox5.Show(); } Redbrush.Dispose(); Bluebrush.Dispose(); yellowbrush.Dispose(); } else { MessageBox.Show("You cannot select an obstacle cell as an endpoint!!!"); return; } } } this.Refresh(); } private void pictureBox1_MouseMove(object sender, MouseEventArgs e) { if (EnterObstacleMode == false) return; if (e.Button == MouseButtons.Middle) { int x = e.X - 20; int y = e.Y - 20; if (x >= 0 && y >= 0 && x < n * step && y < m * step) { int cellx = (int)(x / step); int celly = (int)(y / step); if (cellx > 0 && cellx < n - 1 && celly > 0 && celly < m - 1) { for (int k = 0; k < 2 * K; k++) if (EndPoints[k, 0] == celly && EndPoints[k, 1] == cellx) { MessageBox.Show("Don't click on the source and destination points!"); return; } Obstacle[celly, cellx] = true; //ObstacleChanged = true; SolidBrush blackbrush = new SolidBrush(Color.Black); g.FillRectangle(blackbrush, cellx * step + 20, celly * step + 20, step, step); blackbrush.Dispose(); } } this.Refresh(); } } #endregion #region BUTTON CLICKS // Creat button private void button1_Click(object sender, EventArgs e) { textBox3.Enabled = false; Obstacle = null; EndPoints = null; button2.Hide(); button6.Hide(); button7.Hide(); checkBox1.Hide(); checkBox2.Hide(); checkBox3.Hide(); checkBox4.Hide(); checkBox5.Hide(); button5.Hide(); bmp = new Bitmap(1200, 800); g = Graphics.FromImage(bmp); g.Clear(Color.White); pictureBox1.Image = bmp; CreateGrid(); EnterObstacleMode = true; textBox3.Show(); label2.Show(); button4.Show(); } // Reset Goals private void button3_Click(object sender, EventArgs e) { g.Clear(Color.White); CreateGrid(); SolidBrush blackbrush = new SolidBrush(Color.Black); int i, j; for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (Obstacle[i, j] == true) g.FillRectangle(blackbrush, j * step + 20, i * step + 20, step, step); this.Refresh(); button2.Hide(); button6.Hide(); button7.Hide(); checkBox1.Hide(); checkBox2.Hide(); checkBox3.Hide(); checkBox4.Hide(); checkBox5.Hide(); button3.Hide(); button5.Hide(); for (i = 0; i < 2 * K; i++) { EndPoints[i, 0] = -1; EndPoints[i, 1] = -1; } } //Save button private void button4_Click(object sender, EventArgs e) { SaveFileDialog savDialog = new SaveFileDialog(); savDialog.DefaultExt = "txt"; savDialog.Filter = "Image file (*.tiff)|*.tiff|All files (*.*)|*.*"; savDialog.AddExtension = true; savDialog.Title = "Where do you want to save the file?"; DialogResult result; result = savDialog.ShowDialog(); string savFile = savDialog.FileName; if (result == DialogResult.OK) { string filepath = savFile; bmp.Save(filepath); } savDialog.Dispose(); savDialog = null; } // Find Path private void button2_Click(object sender, EventArgs e) { CreatWorkSpace(); this.Refresh(); Paths = new ArrayList[K]; Dijkstra(); button5.Show(); //textBox3.Enabled=true; } private void CreatWorkSpace() { g.Clear(Color.White); CreateGrid(); SolidBrush blackbrush = new SolidBrush(Color.Black); int i, j; for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (Obstacle[i, j] == true) g.FillRectangle(blackbrush, j * step + 20, i * step + 20, step, step); SolidBrush yellowbrush = new SolidBrush(Color.Yellow); for (int k = 0; k < 2 * K; k++) { j = EndPoints[k, 0]; i = EndPoints[k, 1]; //g.FillRectangle(yellowbrush, i * step + 20, j * step + 20, step, step); SolidBrush Redbrush = new SolidBrush(Color.Red); SolidBrush Bluebrush = new SolidBrush(Color.Blue); if (k < 2) g.FillRectangle(Redbrush, i * step + 20, j * step + 20, step, step); else if (k < 4) g.FillRectangle(Bluebrush, i * step + 20, j * step + 20, step, step); else g.FillRectangle(yellowbrush, i * step + 20, j * step + 20, step, step); string s = ((k / 2) + 1).ToString(); if (k % 2 == 0) s = "s" + s; else s = "g" + s; int fontsize = (int)(step / 6) + 2; if (fontsize < 5) fontsize = 5; g.DrawString(s, new Font("Verdana", fontsize), new SolidBrush(Color.Black), new Point(i * step + 20, j * step + 20)); Redbrush.Dispose(); Bluebrush.Dispose(); } yellowbrush.Dispose(); blackbrush.Dispose(); } // Coordination private void button5_Click(object sender, EventArgs e) { int k1 = 0, k2 = 1; bool whileloop = true; while (whileloop) { whileloop = false; string s1 = "1"; string s2 = "2"; if (InputBox("Robots number", "First robot: ", "Second robot: ", ref s1, ref s2) == DialogResult.Cancel) return; try { k1 = int.Parse(s1); k2 = int.Parse(s2); if (k1 == k2) { MessageBox.Show("You must enter two different robots' number!!!"); whileloop = true; } else if (k1 <= 0 || k2 <= 0 || k1 > K || k2 > K) { MessageBox.Show("There are only " + K.ToString() + " Robots!!!"); whileloop = true; } } catch { MessageBox.Show("Enter two integer numbers"); whileloop = true; } } k1--; k2--; int xcord = Paths[k1].Count / 2; int ycord = Paths[k2].Count / 2; bool[,] CordGraph = new bool[xcord, ycord]; Coordination(CordGraph, xcord, ycord, Paths[k1], Paths[k2]); DrawCordGraph(CordGraph, xcord, ycord); } #endregion #region Dijkstra and Coordination public void DrawCordGraph(bool[,] CordGraph, int xcord, int ycord) { int stepcord=60; if(stepcord> (1000/(xcord-1))) stepcord = (int)(1000 / (xcord-1)); if (stepcord > (600 / (ycord-1))) stepcord = (int)(600 / (ycord-1)); int xlen = stepcord * (xcord-1); int ylen = stepcord * (ycord-1); Bitmap bmpcord = new Bitmap(35 + xlen, 30 + ylen); Graphics gcord = Graphics.FromImage(bmpcord); gcord.Clear(Color.White); Pen bluePen = new Pen(Color.Blue, 1); bluePen.DashStyle = System.Drawing.Drawing2D.DashStyle.Dot; gcord.DrawRectangle(bluePen, 20, 10, xlen, ylen); int i,j; for (i = 0; i < xcord; i++) { gcord.DrawLine(bluePen, i * stepcord + 20, ylen + 10, i * stepcord + 20, 10); gcord.DrawString(i.ToString(), new Font("Verdana", 1+stepcord / 5), new SolidBrush(Color.Black), new Point(i * stepcord + 20-6, ylen + 12)); } for (j = 0; j < ycord; j++) { gcord.DrawLine(bluePen, 20, 10+ (ycord - j - 1) * stepcord, 20 + xlen,10+ (ycord - j - 1) * stepcord); gcord.DrawString(j.ToString(), new Font("Verdana", 1 + stepcord / 5), new SolidBrush(Color.Black), new Point(0, 10 + (ycord-j-1) * stepcord - 7)); } bluePen = new Pen(Color.Blue, 4); Pen blackPen = new Pen(Color.Black, 4); for (i = 0; i < xcord; i++) { for(j=0;j Xresolution / n) step = (int)(Xresolution / n); width = step * n + 20; height = step * m + 20; for (i = 0; i <= m; i++) g.DrawLine(blackPen, 20, 20 + i * step, width, 20 + i * step); for (i = 0; i <= n; i++) g.DrawLine(blackPen, 20 + i * step, 20, 20 + i * step, height); SolidBrush blackbrush = new SolidBrush(Color.Black); for (i = 0; i < n; i++) { Obstacle[0, i] = true; g.FillRectangle(blackbrush, i * step + 20, 20, step, step); } for (i = 0; i < n; i++) { Obstacle[m - 1, i] = true; g.FillRectangle(blackbrush, i * step + 20, ((m - 1) * step) + 20, step, step); } for (i = 0; i < m; i++) { Obstacle[i, 0] = true; g.FillRectangle(blackbrush, 20, i * step + 20, step, step); } for (i = 0; i < m; i++) { Obstacle[i, n - 1] = true; g.FillRectangle(blackbrush, ((n - 1) * step) + 20, i * step + 20, step, step); } this.Refresh(); blackbrush.Dispose(); } private void Dijkstra() { int[,] Cost = new int[m, n]; int k; for (k = 0; k < K; k++) { Paths[k] = new ArrayList(); int sy = EndPoints[2 * k, 0]; int sx = EndPoints[2 * k, 1]; int ty = EndPoints[2 * k+1, 0]; int tx = EndPoints[2 * k+1, 1]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (Obstacle[i, j]) Cost[i, j] = -1; else Cost[i, j] = int.MaxValue; Cost[sy, sx] = 0; bool pathconnected= FindBestPath(Paths[k],Cost, sy,sx,ty,tx); if (pathconnected == false) return; Color pathcolor = Color.Red; if (k == 0) pathcolor = Color.Red; else if (k==1) pathcolor = Color.Blue; else if (k == 2) pathcolor = Color.Green; else if (k == 3) pathcolor = Color.BlueViolet; else if (k == 4) pathcolor = Color.SaddleBrown; else if (k == 5) pathcolor = Color.Orange; else if (k == 6) pathcolor = Color.HotPink; else if (k == 7) pathcolor = Color.MediumPurple; else if (k == 8) pathcolor = Color.DarkOrchid; else pathcolor = Color.Tomato; Showpath(Paths[k], pathcolor, 3+(K-k)/2); this.Refresh(); } } private bool FindBestPath(ArrayList Path, int[,] Cost, int sy, int sx, int ty, int tx) { int x, y; ArrayList List1 = new ArrayList(); ArrayList List2 = new ArrayList(); bool goalfind = false; List1.Add(sy); List1.Add(sx); while (true) { while (List1.Count > 0) { y = (int) List1[0]; List1.RemoveAt(0); x = (int)List1[0]; List1.RemoveAt(0); if (y == ty && x == tx) { goalfind = true; break; } if (Cost[y, x - 1] == int.MaxValue) { List2.Add(y); List2.Add(x - 1); Cost[y, x - 1] = Cost[y, x] + 1; } if (Cost[y, x + 1] == int.MaxValue) { List2.Add(y); List2.Add(x + 1); Cost[y, x + 1] = Cost[y, x] + 1; } if (Cost[y - 1, x] == int.MaxValue) { List2.Add(y - 1); List2.Add(x); Cost[y - 1, x] = Cost[y, x] + 1; } if (Cost[y + 1, x] == int.MaxValue) { List2.Add(y + 1); List2.Add(x); Cost[y + 1, x] = Cost[y, x] + 1; } } if (goalfind == true) break; if (List2.Count == 0) { MessageBox.Show("The Work space must be path connected!! \r\n\t TRY AGAIN"); return false; } while (List2.Count > 0) { List1.Add(List2[0]); List2.RemoveAt(0); } } int dis = (int)Cost[ty, tx]; dis = dis - 1; Path.Add(ty); Path.Add(tx); y=ty; x=tx; Random R = new Random(); while (dis > 0) { int rnumber = R.Next(0, 100); if(rnumber <25) { if (Cost[y, x + 1] == dis) { Path.Add(y); Path.Add(x + 1); x = x + 1; } else if (Cost[y, x - 1] == dis) { Path.Add(y); Path.Add(x - 1); x = x - 1; } else if (Cost[y + 1, x] == dis) { Path.Add(y + 1); Path.Add(x); y = y + 1; } else if (Cost[y - 1, x] == dis) { Path.Add(y - 1); Path.Add(x); y = y - 1; } dis--; } else if (rnumber < 50) { if (Cost[y + 1, x] == dis) { Path.Add(y + 1); Path.Add(x); y = y + 1; } else if (Cost[y - 1, x] == dis) { Path.Add(y - 1); Path.Add(x); y = y - 1; } if (Cost[y, x + 1] == dis) { Path.Add(y); Path.Add(x + 1); x = x + 1; } else if (Cost[y, x - 1] == dis) { Path.Add(y); Path.Add(x - 1); x = x - 1; } dis--; } else if (rnumber < 75) { if (Cost[y, x + 1] == dis) { Path.Add(y); Path.Add(x + 1); x = x + 1; } else if (Cost[y + 1, x] == dis) { Path.Add(y + 1); Path.Add(x); y = y + 1; } else if (Cost[y, x - 1] == dis) { Path.Add(y); Path.Add(x - 1); x = x - 1; } else if (Cost[y - 1, x] == dis) { Path.Add(y - 1); Path.Add(x); y = y - 1; } dis--; } else { if (Cost[y - 1, x] == dis) { Path.Add(y - 1); Path.Add(x); y = y - 1; } else if (Cost[y, x + 1] == dis) { Path.Add(y); Path.Add(x + 1); x = x + 1; } else if (Cost[y, x - 1] == dis) { Path.Add(y); Path.Add(x - 1); x = x - 1; } else if (Cost[y + 1, x] == dis) { Path.Add(y + 1); Path.Add(x); y = y + 1; } dis--; } } Path.Add(sy); Path.Add(sx); Path.Reverse(); return true; } private void Showpath(ArrayList Chrom,Color pathcolor, int size) { int L = Chrom.Count; L = (int)L / 2; int[,] path = new int[L, 2]; int i; for (i = 0; i < L; i++) { path[i, 0] = (int)Chrom[2 * i]; path[i, 1] = (int)Chrom[2 * i + 1]; } //Pen blackPen = new Pen(Color.Black, 1); Pen linePen = new Pen(pathcolor, size); Pen ellipsePen = new Pen(pathcolor, size); //SolidBrush textColor = new SolidBrush(Color.Red); for (i = 0; i < L; i++) { int x1 = path[i, 0] * step + 20 + (step / 2); int y1 = path[i, 1] * step + 20 + (step / 2); g.DrawEllipse(ellipsePen, x1 - 1, y1 - 1, 2, 2); if (i < L - 1) { int x2 = path[i + 1, 0] * step + 20 + (step / 2); int y2 = path[i + 1, 1] * step + 20 + (step / 2); Point startPoint = new Point(x1, y1); Point endPoint = new Point(x2, y2); g.DrawLine(linePen, startPoint, endPoint); //g1.DrawLine(linePen, x1, y1, x2, y2); } } //string S = "\r\n"; //S += "\r\nMinC: "; //S += OBJ0.ToString(); //S += "\r\nLen: "; //S += OBJ1.ToString(); //g1.DrawString(S, // new Font("Verdana", (int)(15)), // textColor, // new Point((int)(770), (int)((10)))); linePen.Dispose(); ellipsePen.Dispose(); } private void Coordination(bool[,] CordGraph, int xcord, int ycord, ArrayList P1, ArrayList P2) { int i, j; for (i = 0; i < 2*xcord; i+=2) { int y1 = (int)P1[i]; int x1 = (int)P1[i+1]; for (j = 0; j < 2*ycord; j+=2) { int y2 = (int)P2[j]; int x2 = (int)P2[j + 1]; if (x1 == x2 && y1 == y2) CordGraph[(int)(i/2), (int)(j/2)] = true; } } } #endregion #region Especiall cases private void button6_Click(object sender, EventArgs e) { CreatWorkSpace(); this.Refresh(); Paths = new ArrayList[K]; if (Dijkstra2() == false) return; int L1 = Paths[0].Count / 2; int L2 = Paths[1].Count / 2; int[,] P1 = new int[L1, 2]; int[,] P2 = new int[L2, 2]; int i, j; for (i = 0; i < L1; i++) { P1[i, 0] = (int)Paths[0][2 * i]; P1[i, 1] = (int)Paths[0][2 * i + 1]; } for (i = 0; i < L2; i++) { P2[i, 0] = (int)Paths[1][2 * i]; P2[i, 1] = (int)Paths[1][2 * i + 1]; } bool Existdegree3 = false; for ( i = 0; i < m && Existdegree3 == false; i++) for (j = 0; j < n && Existdegree3 == false; j++) if (Obstacle[i, j] == false) { int degree = 0; if (Obstacle[i, j - 1] == false) degree++; if (Obstacle[i, j + 1] == false) degree++; if (Obstacle[i - 1, j] == false) degree++; if (Obstacle[i + 1, j] == false) degree++; if (degree > 2) Existdegree3 = true; } if (Existdegree3 == true) // There is at least one PARKING { MinMaxAlgo(P1, L1, P2, L2); } else { bool Existdegree1 = false; for (i = 0; i < m && Existdegree1 == false; i++) for (j = 0; j < n && Existdegree1 == false; j++) if (Obstacle[i, j] == false) { int degree = 0; if (Obstacle[i, j - 1] == false) degree++; if (Obstacle[i, j + 1] == false) degree++; if (Obstacle[i - 1, j] == false) degree++; if (Obstacle[i + 1, j] == false) degree++; if (degree == 1) Existdegree1 = true; } if (Existdegree1 == true) // The Work space is a Tree without PARKING { int collision_cell= SimpleCollisionChecker(P1, L1, P2, L2); if (collision_cell >= 0) { MessageBox.Show("There is no feasible solution"); return; } else { Color pathcolor = Color.Red; Showpath(Paths[0], pathcolor, 8); pathcolor = Color.Blue; Showpath(Paths[1], pathcolor, 4); } } else // The Work space is exactly a cycle (all vertices has degree two) { int collision_cell = SimpleCollisionChecker(P1, L1, P2, L2); if (collision_cell == -1) { Color pathcolor = Color.Red; Showpath(Paths[0], pathcolor, 8); pathcolor = Color.Blue; Showpath(Paths[1], pathcolor, 4); } else { int xobs = P1[collision_cell, 0]; int yobs = P1[collision_cell, 1]; ArrayList tempP1 = new ArrayList(); int sy = EndPoints[0, 0]; int sx = EndPoints[0, 1]; int ty = EndPoints[1, 0]; int tx = EndPoints[1, 1]; if (sy == yobs && sx == xobs) { xobs = P1[collision_cell + 1, 0]; yobs = P1[collision_cell + 1, 1]; } else if (ty == yobs && tx == xobs) { xobs = P1[collision_cell-1, 0]; yobs = P1[collision_cell-1, 1]; } Obstacle[yobs, xobs] = true; //Obstacle[EndPoints[2, 0], EndPoints[2, 1]] = true; Dijkstra3(tempP1,sx,sy,tx,ty); //Obstacle[EndPoints[2, 0], EndPoints[2, 1]] = false; ArrayList tempP2 = new ArrayList(); sy = EndPoints[2, 0]; sx = EndPoints[2, 1]; ty = EndPoints[3, 0]; tx = EndPoints[3, 1]; if (sy == yobs && sx == xobs) { xobs = P2[collision_cell + 1, 0]; yobs = P2[collision_cell + 1, 1]; } else if (ty == yobs && tx == xobs) { xobs = P2[collision_cell - 1, 0]; yobs = P2[collision_cell - 1, 1]; } //Obstacle[EndPoints[0, 0], EndPoints[0, 1]] = true; Dijkstra3(tempP2, sx, sy, tx, ty); //Obstacle[EndPoints[0, 0], EndPoints[0, 1]] = false; Obstacle[yobs, xobs] = false; int max1 = L2; if (L2 < tempP1.Count / 2) max1 = tempP1.Count / 2; int max2 = L1; if (L1 < tempP2.Count / 2) max2 = tempP2.Count / 2; if (max1 > max2) { Color pathcolor = Color.Red; Showpath(Paths[0], pathcolor, 8); pathcolor = Color.Blue; Showpath(tempP2, pathcolor, 4); Paths[1].Clear(); while(tempP2.Count>0) { Paths[1].Add(tempP2[0]); tempP2.RemoveAt(0); } } else { Color pathcolor = Color.Red; Showpath(tempP1, pathcolor, 8); pathcolor = Color.Blue; Showpath(Paths[1], pathcolor, 4); Paths[0].Clear(); while (tempP2.Count > 0) { Paths[0].Add(tempP1[0]); tempP1.RemoveAt(0); } } } } } this.Refresh(); } private void Dijkstra3(ArrayList tempPath, int sx, int sy, int tx, int ty) { int[,] Cost = new int[m, n]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (Obstacle[i, j]) Cost[i, j] = -1; else Cost[i, j] = int.MaxValue; Cost[sy, sx] = 0; bool pathconnected = FindBestPath(tempPath, Cost, sy, sx, ty, tx); } private int SimpleCollisionChecker(int[,] P1, int L1, int[,] P2, int L2) { int i, j; for (i = 1, j = 1; i < L1 || j < L2; ) { if (P1[i, 0] == P2[j, 0] && P1[i, 1] == P2[j, 1]) return i - 1; if (P1[i - 1, 0] == P2[j, 0] && P1[i - 1, 1] == P2[j, 1] && P1[i, 0] == P2[j - 1, 0] && P1[i, 1] == P2[j - 1, 1]) return i - 1; i++; j++; if (i == L1 && j == L2) break; if (i == L1) i--; if (j == L2) j--; } return -1; } private bool Dijkstra2() { int[,] Cost = new int[m, n]; int k; for (k = 0; k < K; k++) { Paths[k] = new ArrayList(); int sy = EndPoints[2 * k, 0]; int sx = EndPoints[2 * k, 1]; int ty = EndPoints[2 * k + 1, 0]; int tx = EndPoints[2 * k + 1, 1]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (Obstacle[i, j]) Cost[i, j] = -1; else Cost[i, j] = int.MaxValue; Cost[sy, sx] = 0; bool pathconnected = FindBestPath(Paths[k], Cost, sy, sx, ty, tx); if (pathconnected == false) return false; } return true; } #endregion #region Find Common Time Cells private void button7_Click(object sender, EventArgs e) { CreatWorkSpace(); this.Refresh(); Paths = new ArrayList[K]; if (Dijkstra2() == false) return; int L1 = Paths[0].Count / 2; int L2 = Paths[1].Count / 2; int[,] P1 = new int[L1, 2]; int[,] P2 = new int[L2, 2]; int i, j; for (i = 0; i < L1; i++) { P1[i, 0] = (int)Paths[0][2 * i]; P1[i, 1] = (int)Paths[0][2 * i + 1]; } for (i = 0; i < L2; i++) { P2[i, 0] = (int)Paths[1][2 * i]; P2[i, 1] = (int)Paths[1][2 * i + 1]; } ComputeCT(P1, L1, P2, L2); } private void ComputeCT(int[,] P1, int L1, int[,] P2, int L2) { int[,] s1 = new int[1, 2]; s1[0, 0] = P1[0, 0]; s1[0, 1] = P1[0, 1]; int[,] t1 = new int[1, 2]; t1[0, 0] = P1[L1 - 1, 0]; t1[0, 1] = P1[L1 - 1, 1]; int[,] s2 = new int[1, 2]; s2[0, 0] = P2[0, 0]; s2[0, 1] = P2[0, 1]; int[,] t2 = new int[1, 2]; t2[0, 0] = P2[L2 - 1, 0]; t2[0, 1] = P2[L2 - 1, 1]; int[,] Costs1 = new int[m, n]; FindCT(Costs1, s1); int[,] Costs2 = new int[m, n]; FindCT(Costs2, s2); int[,] Costt1 = new int[m, n]; FindCT(Costt1, t1); int[,] Costt2 = new int[m, n]; FindCT(Costt2, t2); int SPs1t1 = Costs1[t1[0, 1], t1[0, 0]]; int SPs2t2 = Costs2[t2[0, 1], t2[0, 0]]; int i, j; bool[,] CT = new bool[m, n]; for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (Obstacle[i, j] == false) if (Costs1[i, j] == Costs2[i, j] && Costt1[i, j] == Costt2[i, j]) if (Costs1[i, j] + Costt1[i, j] == SPs1t1 && SPs2t2 == SPs1t1) CT[i, j] = true; ShowCTcells(CT, Color.GreenYellow); if (checkBox1.Checked) { ShowCT(Costs1, 20, -4,s1,t1,Color.Red); //Main //ShowCT(Costs1, 30, -4, s1, t1, Color.Red); //ShowCT(Costt1, 20, 6,s1,t1,Color.Red); //Main ShowCT(Costs2, 20, 19, s2, t2, Color.Blue);//Main //ShowCT(Costs2, 30, 32, s2, t2, Color.Blue); //ShowCT(Costt2, 20, 29, s2,t2,Color.Blue);//Main } if (checkBox2.Checked) { int[,] UnCommonCells1 = new int[m, n]; FindCommonCells(UnCommonCells1, CT, Costs1, s1); int[,] UnCommonCells2 = new int[m, n]; FindCommonCells(UnCommonCells2, CT, Costs2, s2); ShowCT(UnCommonCells1, 0, -4, s1, t1, Color.Red);//main //ShowCT(UnCommonCells1, 0, -4, s1, t1, Color.Red); ShowCT(UnCommonCells2, 0, 19, s2, t2, Color.Blue);//main //ShowCT(UnCommonCells2, 0, 32, s2, t2, Color.Blue); } if (checkBox4.Checked) { Pen PurplePen = new Pen(Color.Purple, 3); Pen BlueVioletPen = new Pen(Color.LightBlue, 3); for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (Obstacle[i, j] == false) if (Costs1[i, j] < Costs2[i, j]) g.DrawRectangle(PurplePen, j * step + 20, i * step + 20, step, step); else if (Costs1[i, j] > Costs2[i, j]) g.DrawRectangle(BlueVioletPen, j * step + 20, i * step + 20, step, step); this.Refresh(); PurplePen.Dispose(); BlueVioletPen.Dispose(); } if (checkBox5.Checked) { Pen PurplePen = new Pen(Color.Pink, 2); Pen BlueVioletPen = new Pen(Color.Cyan, 2); for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (Obstacle[i, j] == false) if (Costt1[i, j] < Costt2[i, j]) g.DrawRectangle(PurplePen, j * step + 20, i * step + 20, step, step); else if (Costt1[i, j] > Costt2[i, j]) g.DrawRectangle(BlueVioletPen, j * step + 20, i * step + 20, step, step); this.Refresh(); PurplePen.Dispose(); BlueVioletPen.Dispose(); } if (checkBox3.Checked) { int[,] furs1 = new int[1, 2]; FindFurthest(CT, Costs1, furs1); int[,] furt1 = new int[1, 2]; FindFurthest(CT, Costt1, furt1); int[,] furs2 = new int[1, 2]; FindFurthest(CT, Costs2, furs2); int[,] furt2 = new int[1, 2]; FindFurthest(CT, Costt2, furt2); Pen RedPen = new Pen(Color.Red, 3); Pen bluePen = new Pen(Color.Blue, 2); g.DrawRectangle(RedPen, furs1[0, 0] * step + 20, furs1[0, 1] * step + 20, step, step); g.DrawRectangle(RedPen, furt1[0, 0] * step + 20, furt1[0, 1] * step + 20, step, step); g.DrawRectangle(bluePen, furs2[0, 0] * step + 20, furs2[0, 1] * step + 20, step, step); g.DrawRectangle(bluePen, furt2[0, 0] * step + 20, furt2[0, 1] * step + 20, step, step); this.Refresh(); RedPen.Dispose(); bluePen.Dispose(); } } private void FindFurthest(bool[,] CT, int[,] Cost, int[,] fur) { int i, j; int max=0; for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (CT[i, j]) if (Cost[i, j] > max) if ( (Cost[i - 1, j] == Cost[i, j] - 1 && !CT[i-1, j]) || (Cost[i + 1, j] == Cost[i, j] - 1 && !CT[i+1, j]) || (Cost[i, j - 1] == Cost[i, j] - 1 && !CT[i, j-1]) || (Cost[i, j + 1] == Cost[i, j] - 1 && !CT[i, j+1]) ) { max = Cost[i, j]; fur[0, 0] = j; fur[0, 1] = i; } } private void FindCommonCells(int[,] UnCommonCells, bool[,] CT, int[,] Cost, int[,] Source) { int sx = Source[0, 0]; int sy = Source[0, 1]; int i, j, l; for (i = 0; i < m; i++) for (j = 0; j < n; j++) UnCommonCells[i, j] = int.MinValue; UnCommonCells[sy, sx] = 0; l = 0; bool whileloop = true; while (whileloop) { whileloop = false; l++; for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (Cost[i, j] == l) { int max = 0; if (Cost[i, j - 1] == l - 1 && UnCommonCells[i, j - 1] > max) max = UnCommonCells[i, j - 1]; if (Cost[i, j + 1] == l - 1 && UnCommonCells[i, j + 1] > max) max = UnCommonCells[i, j + 1]; if (Cost[i - 1, j] == l - 1 && UnCommonCells[i - 1, j] > max) max = UnCommonCells[i - 1, j]; if (Cost[i + 1, j] == l - 1 && UnCommonCells[i + 1, j] > max) max = UnCommonCells[i + 1, j]; if (CT[i, j] == false) max = max + 1; UnCommonCells[i, j] = max; whileloop = true; } } } private void FindCT(int[,] Cost, int[,] Source) { int sx = Source[0, 0]; int sy = Source[0, 1]; int i, j; for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (Obstacle[i, j]) Cost[i, j] = -1; else Cost[i, j] = int.MaxValue; Cost[sy, sx] = 0; int x, y; ArrayList List1 = new ArrayList(); ArrayList List2 = new ArrayList(); List1.Add(sy); List1.Add(sx); while (true) { while (List1.Count > 0) { y = (int)List1[0]; List1.RemoveAt(0); x = (int)List1[0]; List1.RemoveAt(0); if (Cost[y, x - 1] == int.MaxValue) { List2.Add(y); List2.Add(x - 1); Cost[y, x - 1] = Cost[y, x] + 1; } if (Cost[y, x + 1] == int.MaxValue) { List2.Add(y); List2.Add(x + 1); Cost[y, x + 1] = Cost[y, x] + 1; } if (Cost[y - 1, x] == int.MaxValue) { List2.Add(y - 1); List2.Add(x); Cost[y - 1, x] = Cost[y, x] + 1; } if (Cost[y + 1, x] == int.MaxValue) { List2.Add(y + 1); List2.Add(x); Cost[y + 1, x] = Cost[y, x] + 1; } } if (List2.Count == 0) break; while (List2.Count > 0) { List1.Add(List2[0]); List2.RemoveAt(0); } } } private void ShowCT(int[,] Costs, int xshowshift, int yshowshift, int[,] s, int[,] t, Color Colortext) { int i, j; for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (Costs[i, j] > -1) { string S = (Costs[i, j]).ToString(); if ((i == s[0, 1] && j == s[0, 0]) || (i == t[0, 1] && j == t[0, 0])) { g.DrawString(S, new Font("Verdana", (step / 6) + 1), //6 new SolidBrush(Color.Black), new Point((int)(j * step + 25 + xshowshift), (int)((i * step + 25 + yshowshift)))); } else { g.DrawString(S, new Font("Verdana", (step / 6) + 1), new SolidBrush(Colortext), new Point((int)(j * step + 25 + xshowshift), (int)((i * step + 25 + yshowshift)))); } } this.Refresh(); } private void ShowCTcells(bool[,] CT, Color CTcolor) { int i, j; SolidBrush brush = new SolidBrush(CTcolor); for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (CT[i, j] == true) g.FillRectangle(brush, j * step + 20, i * step + 20, step, step); this.Refresh(); brush.Dispose(); } #endregion private void MinMaxAlgo(int[,] P1, int L1, int[,] P2, int L2) { int[,] s1 = new int[1, 2]; s1[0, 0] = P1[0, 0]; s1[0, 1] = P1[0, 1]; int[,] t1 = new int[1, 2]; t1[0, 0] = P1[L1 - 1, 0]; t1[0, 1] = P1[L1 - 1, 1]; int[,] s2 = new int[1, 2]; s2[0, 0] = P2[0, 0]; s2[0, 1] = P2[0, 1]; int[,] t2 = new int[1, 2]; t2[0, 0] = P2[L2 - 1, 0]; t2[0, 1] = P2[L2 - 1, 1]; int[,] Costs1 = new int[m, n]; FindCT(Costs1, s1); int[,] Costs2 = new int[m, n]; FindCT(Costs2, s2); int[,] Costt1 = new int[m, n]; FindCT(Costt1, t1); int[,] Costt2 = new int[m, n]; FindCT(Costt2, t2); int SPs1t1 = Costs1[t1[0, 1], t1[0, 0]]; int SPs2t2 = Costs2[t2[0, 1], t2[0, 0]]; int i, j; bool[,] CT = new bool[m, n]; for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (Obstacle[i, j] == false) if (Costs1[i, j] == Costs2[i, j] && Costt1[i, j] == Costt2[i, j]) if (Costs1[i, j] + Costt1[i, j] == SPs1t1 && SPs2t2 == SPs1t1) CT[i, j] = true; ShowCTcells(CT, Color.GreenYellow); ArrayList Path1 = new ArrayList(); ArrayList Path11 = new ArrayList(); ArrayList Path2 = new ArrayList(); ArrayList Path22 = new ArrayList(); Color pathcolor = Color.Red; int[,] UnCommonCells1 = new int[m, n]; FindCommonCells(UnCommonCells1, CT, Costs1, s1); int[,] UnCommonCells2 = new int[m, n]; FindCommonCells(UnCommonCells2, CT, Costs2, s2); //if (L1 == L2) //{ // int[,] UnCommonCells1 = new int[m, n]; // FindCommonCells(UnCommonCells1, CT, Costs1, s1); // int[,] UnCommonCells2 = new int[m, n]; // FindCommonCells(UnCommonCells2, CT, Costs2, s2); // InteligentPathFinder(Path1, s1, t1, Costs1,UnCommonCells1, Path2, s2, t2, Costs2,UnCommonCells2, CT); // Showpath(Path1, pathcolor, 5); // pathcolor = Color.Blue; // Showpath(Path2, pathcolor, 3); //} if (L1 == L2) { //BInteligentBFS(Path2, s2, t2, Costs2, CT, UnCommonCells2); InteligentBFS(Path1, s1, t1, Costs1, CT, UnCommonCells1); int[,] Costs22 = new int[m, n]; //for (i = 0; i < m; i++) // for (j = 0; j < n; j++) // Costs22[i, j] = int.MaxValue; for (i = 0; i < Path1.Count; i += 2) { int x = (int)Path1[i]; int y = (int)Path1[i + 1]; if (CT[y, x] == true) Obstacle[y, x] = true; } FindCT(Costs22, s2); for (i = 0; i < Path1.Count; i += 2) { int x = (int)Path1[i]; int y = (int)Path1[i + 1]; if (CT[y, x] == true) Obstacle[y, x] = false; } if (Costs22[t2[0, 1], t2[0, 0]] == L1 - 1) { Showpath(Path1, pathcolor, 5); UsualBFS(Path22, s2, t2, Costs22); pathcolor = Color.Blue; Showpath(Path22, pathcolor, 3); } else { //BInteligentBFS(Path2, s2, t2, Costs2, CT, UnCommonCells2); InteligentBFS(Path2, s2, t2, Costs2, CT, UnCommonCells2); int[,] Costs11 = new int[m, n]; //for (i = 0; i < m; i++) // for (j = 0; j < n; j++) // Costs11[i, j] = int.MaxValue; for (i = 0; i < Path2.Count; i += 2) { int x = (int)Path2[i]; int y = (int)Path2[i + 1]; if (CT[y, x] == true) Obstacle[y, x] = true; } FindCT(Costs11, s1); for (i = 0; i < Path2.Count; i += 2) { int x = (int)Path2[i]; int y = (int)Path2[i + 1]; if (CT[y, x] == true) Obstacle[y, x] = false; } if (Costs11[t1[0, 1], t1[0, 0]] == L1 - 1) { UsualBFS(Path11, s1, t1, Costs11); Showpath(Path11, pathcolor, 5); pathcolor = Color.Blue; Showpath(Path2, pathcolor, 3); } else { MessageBox.Show("There is no shortest Path \r\n Use scheduling"); Showpath(Path1, pathcolor, 5); pathcolor = Color.Blue; Showpath(Path2, pathcolor, 3); } } } else { UsualBFS(Path1, s1, t1, Costs1); UsualBFS(Path2, s2, t2, Costs2); Showpath(Path1, pathcolor, 5); pathcolor = Color.Blue; Showpath(Path2, pathcolor, 3); } this.Refresh(); } private void BInteligentBFS(ArrayList Path, int[,] s, int[,] t, int[,] Cost, bool[,] CT, int[,] UnCommonCells) { int ty = t[0, 1]; int tx = t[0, 0]; int sy = s[0, 1]; int sx = s[0, 0]; int dis = (int)Cost[ty, tx]; dis = dis - 1; Path.Add(ty); Path.Add(tx); int y = ty; int x = tx; while (dis > 0) { int[] Go = new int[4]; Go[0] = -1; Go[1] = -1; Go[2] = -1; Go[3] = -1; if (Cost[y, x + 1] == dis) Go[0] = UnCommonCells[y, x + 1]; if (Cost[y, x - 1] == dis) Go[1] = UnCommonCells[y, x - 1]; if (Cost[y + 1, x] == dis) Go[2] = UnCommonCells[y + 1, x]; if (Cost[y - 1, x] == dis) Go[3] = UnCommonCells[y - 1, x]; int i, maxgo = -1; for (i = 0; i < 4; i++) if (Go[i] > maxgo) maxgo = Go[i]; if (Go[0] == maxgo && CT[y, x + 1] == false) { Path.Add(y); Path.Add(x + 1); x = x + 1; } else if (Go[1] == maxgo && CT[y, x - 1] == false) { Path.Add(y); Path.Add(x - 1); x = x - 1; } else if (Go[2] == maxgo && CT[y + 1, x] == false) { Path.Add(y + 1); Path.Add(x); y = y + 1; } else if (Go[3] == maxgo && CT[y - 1, x] == false) { Path.Add(y - 1); Path.Add(x); y = y - 1; } else { int[] GoBound = new int[4]; GoBound[0] = 0; GoBound[1] = 0; GoBound[2] = 0; GoBound[3] = 0; if (Go[0] == maxgo) { GoBound[0]++; if (Obstacle[y - 1, x + 1] || CT[y - 1, x + 1] == false) GoBound[0]++; if (Obstacle[y + 1, x + 1] || CT[y + 1, x +1] == false) GoBound[0]++; if (Obstacle[y, x + 2] || CT[y, x + 2] == false) GoBound[0]++; } if (Go[1] == maxgo) { GoBound[1]++; if (Obstacle[y - 1, x - 1] || CT[y - 1, x - 1] == false) GoBound[1]++; if (Obstacle[y + 1, x - 1] || CT[y + 1, x - 1] == false) GoBound[1]++; if (Obstacle[y, x - 2] || CT[y, x - 2] == false) GoBound[1]++; } if (Go[2] == maxgo) { GoBound[2]++; if (Obstacle[y + 1, x - 1] || CT[y + 1, x - 1] == false) GoBound[2]++; if (Obstacle[y + 1, x + 1] || CT[y + 1, x + 1] == false) GoBound[2]++; if (Obstacle[y + 2, x] || CT[y + 2, x] == false) GoBound[2]++; } if (Go[3] == maxgo) { GoBound[3]++; if (Obstacle[y - 1, x - 1] || CT[y - 1, x - 1] == false) GoBound[3]++; if (Obstacle[y - 1, x + 1] || CT[y - 1, x + 1] == false) GoBound[3]++; if (Obstacle[y - 2, x] || CT[y - 2, x] == false) GoBound[3]++; } int maxgobound = 0; for (i = 0; i < 4; i++) if (GoBound[i] > maxgobound) maxgobound = GoBound[i]; if (GoBound[0] == maxgobound) { Path.Add(y); Path.Add(x + 1); x = x + 1; } else if (GoBound[1] == maxgobound) { Path.Add(y); Path.Add(x - 1); x = x - 1; } else if (GoBound[2] == maxgobound) { Path.Add(y + 1); Path.Add(x); y = y + 1; } else if (GoBound[3] == maxgobound) { Path.Add(y - 1); Path.Add(x); y = y - 1; } } dis--; } Path.Add(sy); Path.Add(sx); Path.Reverse(); } private void InteligentBFS(ArrayList Path, int[,] s, int[,] t, int[,] Cost, bool[,] CT, int[,] UnCommonCells) { int ty = t[0, 1]; int tx = t[0, 0]; int sy = s[0, 1]; int sx = s[0, 0]; int dis = (int)Cost[ty, tx]; dis = dis - 1; Path.Add(ty); Path.Add(tx); int y = ty; int x = tx; while (dis > 0) { int[] Go = new int[4]; Go[0] = -1; Go[1] = -1; Go[2] = -1; Go[3] = -1; if (Cost[y, x + 1] == dis) Go[0] = UnCommonCells[y, x + 1]; if (Cost[y, x - 1] == dis) Go[1] = UnCommonCells[y, x - 1]; if (Cost[y + 1, x] == dis) Go[2] = UnCommonCells[y + 1, x]; if (Cost[y - 1, x] == dis) Go[3] = UnCommonCells[y - 1, x]; int i, maxgo = -1; for (i = 0; i < 4; i++) if (Go[i] > maxgo) maxgo = Go[i]; if (Go[0] == maxgo && CT[y, x + 1] == false) { Path.Add(y); Path.Add(x + 1); x = x + 1; } else if (Go[1] == maxgo && CT[y, x - 1] == false) { Path.Add(y); Path.Add(x - 1); x = x - 1; } else if (Go[2] == maxgo && CT[y + 1, x] == false) { Path.Add(y + 1); Path.Add(x); y = y + 1; } else if (Go[3] == maxgo && CT[y - 1, x] == false) { Path.Add(y - 1); Path.Add(x); y = y - 1; } else if (Go[0] == maxgo) { Path.Add(y); Path.Add(x + 1); x = x + 1; } else if (Go[1] == maxgo) { Path.Add(y); Path.Add(x - 1); x = x - 1; } else if (Go[2] == maxgo) { Path.Add(y + 1); Path.Add(x); y = y + 1; } else if (Go[3] == maxgo) { Path.Add(y - 1); Path.Add(x); y = y - 1; } dis--; } Path.Add(sy); Path.Add(sx); Path.Reverse(); } private void UsualBFS(ArrayList Path, int[,] s, int[,] t, int[,] Cost) { int ty = t[0, 1]; int tx = t[0, 0]; int sy = s[0, 1]; int sx = s[0, 0]; int dis = (int)Cost[ty, tx]; dis = dis - 1; Path.Add(ty); Path.Add(tx); int y = ty; int x = tx; while (dis > 0) { if (Cost[y, x + 1] == dis) { Path.Add(y); Path.Add(x + 1); x = x + 1; } else if (Cost[y, x - 1] == dis) { Path.Add(y); Path.Add(x - 1); x = x - 1; } else if (Cost[y + 1, x] == dis) { Path.Add(y + 1); Path.Add(x); y = y + 1; } else if (Cost[y - 1, x] == dis) { Path.Add(y - 1); Path.Add(x); y = y - 1; } dis--; } Path.Add(sy); Path.Add(sx); Path.Reverse(); } private void InteligentPathFinder(ArrayList Path1, int[,] s1, int[,] t1, int[,] Cost1,int [,] UnCommonCells1, ArrayList Path2, int[,] s2, int[,] t2, int[,] Cost2, int [,]UnCommonCells2, bool[,] CT) { int ty1 = t1[0, 1]; int tx1 = t1[0, 0]; int sy1 = s1[0, 1]; int sx1 = s1[0, 0]; int ty2 = t2[0, 1]; int tx2 = t2[0, 0]; int sy2 = s2[0, 1]; int sx2 = s2[0, 0]; int dis = (int)Cost1[ty1, tx1]; dis = dis - 1; Path1.Add(ty1); Path1.Add(tx1); int y1 = ty1; int x1 = tx1; Path2.Add(ty2); Path2.Add(tx2); int y2 = ty2; int x2 = tx2; int[,] Delta1 = new int[4, 2]; bool[] Feasible1 = new bool[4]; int[,] Delta2 = new int[4, 2]; bool[] Feasible2 = new bool[4]; Delta1[0, 0] = 0; Delta1[0, 1] = -1; Delta1[1, 0] = 0; Delta1[1, 1] = +1; Delta1[2, 0] = -1; Delta1[2, 1] = 0; Delta1[3, 0] = +1; Delta1[3, 1] = 0; Delta2[0, 0] = 0; Delta2[0, 1] = -1; Delta2[1, 0] = 0; Delta2[1, 1] = +1; Delta2[2, 0] = -1; Delta2[2, 1] = 0; Delta2[3, 0] = +1; Delta2[3, 1] = 0; int i,j; while (dis > 0) { for (i = 0; i < 4;i++) if(Cost1[y1+Delta1[i,0], x1+Delta1[i,1]]==dis) Feasible1[i]=true; else Feasible1[i]=false; for (i = 0; i < 4; i++) if (Cost2[y2 + Delta2[i, 0], x2 + Delta2[i, 1]] == dis) Feasible2[i] = true; else Feasible2[i] = false; //if (Cost[y, x + 1] == dis && CT[y, x + 1] == false) //{ // Path.Add(y); // Path.Add(x + 1); // x = x + 1; //} //else if (Cost[y, x - 1] == dis && CT[y, x - 1] == false) //{ // Path.Add(y); // Path.Add(x - 1); // x = x - 1; //} //else if (Cost[y + 1, x] == dis && CT[y + 1, x] == false) //{ // Path.Add(y + 1); // Path.Add(x); // y = y + 1; //} //else if (Cost[y - 1, x] == dis && CT[y - 1, x] == false) //{ // Path.Add(y - 1); // Path.Add(x); // y = y - 1; //} //else if (Cost[y, x + 1] == dis) //{ // Path.Add(y); // Path.Add(x + 1); // x = x + 1; //} //else if (Cost[y, x - 1] == dis) //{ // Path.Add(y); // Path.Add(x - 1); // x = x - 1; //} //else if (Cost[y + 1, x] == dis) //{ // Path.Add(y + 1); // Path.Add(x); // y = y + 1; //} //else if (Cost[y - 1, x] == dis) //{ // Path.Add(y - 1); // Path.Add(x); // y = y - 1; //} dis--; } Path1.Add(sy1); Path1.Add(sx1); Path1.Reverse(); Path2.Add(sy2); Path2.Add(sx2); Path2.Reverse(); } private void pictureBox1_Click(object sender, EventArgs e) { } private void checkBox1_CheckedChanged(object sender, EventArgs e) { } } }